import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Collections;

public class HuffTree {
    public static void main(String[] args) {
        //创建哈夫曼树
        //思路：把数组里的数据变成结点放到集合里
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        ArrayList<HuffNode> list=new ArrayList<>();
        list=TurnNode(arr,list);//将数据变成结点
        //创建哈夫曼树
        HuffNode root=CreHuffTree(list);
        //前序遍历
        Pre(root);
    }

    //创建哈夫曼树
    public static HuffNode CreHuffTree(ArrayList<HuffNode> list){
        //最后的时候只会剩下新加的结点67
        while(list.size()>1){
            //先排序
            Collections.sort(list);
            //选出最小的的两个节点--小在左，大在右
            HuffNode leftNode=list.get(0);
            HuffNode rightNode=list.get(1);
            //创建新的结点，结点的data是左右子树之和
            HuffNode parent=new HuffNode(leftNode.getData()+rightNode.getData());
            //再将左子树右子树挂好
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            //将集合里的那两个节点删除
            list.remove(leftNode);
            list.remove(rightNode);
            //再将新结点添加到集合中，进行下次排序操作
            list.add(parent);
        }
        return list.get(0);
    }
    //前序遍历
    public static void Pre(HuffNode root){
        //这里的根节点其实就是集合里剩下的最后一个结点
        if(root!=null){
            root.PreOrder();
        }

    }

    public static ArrayList<HuffNode> TurnNode(int[] arr,ArrayList<HuffNode> list){
        for (int i = 0; i < arr.length; i++) {
            list.add(new HuffNode(arr[i]));//将数据放到结点中，再将结点添加到集合里
        }
        return list;
    }
}
class HuffNode implements Comparable<HuffNode>{
   private int data;
   private HuffNode left;
   private HuffNode right;

   //构造器
    public HuffNode(int data){
        this.data=data;
    }
    //前序遍历
    public void PreOrder(){
        System.out.print(this.data+" ");
        //向左子树遍历
        if(this.left!=null){
            this.left.PreOrder();
        }
        //向右子树遍历
        if(this.right!=null){
            this.right.PreOrder();
        }
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setLeft(HuffNode left) {
        this.left = left;
    }

    public HuffNode getLeft() {
        return left;
    }

    public void setRight(HuffNode right) {
        this.right = right;
    }

    public HuffNode getRight() {
        return right;
    }

    @Override
    public int compareTo(HuffNode o) {
        return this.data-o.data;
    }
}